package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2332. 坐上公交的最晚时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/11 10:34
 */
public class LatestTimeCatchTheBus {

    public static void main(String[] args) {
        LatestTimeCatchTheBus test = new LatestTimeCatchTheBus();

        // 16
//        int[] buses = {10, 20};
//        int[] passengers = {2, 17, 18, 19};
//        int capacity = 2;

        // 20
//        int[] buses = {20, 30, 10};
//        int[] passengers = {19, 13, 26, 4, 25, 11, 21};
//        int capacity = 2;

        // 10
//        int[] buses = {10, 20, 30};
//        int[] passengers = {1, 2, 11};
//        int capacity = 1;

        // 1
//        int[] buses = {3};
//        int[] passengers = {2,3};
//        int capacity = 2;

        //
        int[] buses = {3, 4, 2};
        int[] passengers = {2};
        int capacity = 3;

        // 1
//        int[] buses = {2};
//        int[] passengers = {2};
//        int capacity = 2;

        // 5
//        int[] buses = {5};
//        int[] passengers = {7,8};
//        int capacity = 1;

        // 11
//        int[] buses = {18, 8, 3, 12, 9, 2, 7, 13, 20, 5};
//        int[] passengers = {13, 10, 8, 4, 12, 14, 18, 19, 5, 2, 30, 34};
//        int capacity = 1;

        // 19
//        int[] buses = {14, 10, 4, 5, 7, 2, 11, 19, 16, 9};
//        int[] passengers = {3, 39, 45, 30, 40, 50, 13, 15, 34, 5};
//        int capacity = 3;

        int i = test.latestTimeCatchTheBus(buses, passengers, capacity);
        System.out.println(i);
    }

    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int m = buses.length;
        int n = passengers.length;
        int v = buses[m - 1];
        if (passengers[0] > buses[m - 1]) {
            return v;
        }
        int count;
        int j = 0;
        int i = 0;
        u:
        for (; i < m - 1; i++) {
            count = 0;
            int r = buses[i];
            while (true) {
                if (passengers[j] <= r) {
                    count++;
                    if (count == capacity) {
                        j++;
                        break;
                    }
                } else {
                    break;
                }
                j++;
                if (j == n) {
                    break u;
                }
            }
        }
        if (j == n) {
            return v;
        }
        while (capacity > 0) {
            if (passengers[j] <= v) {
                capacity--;
                j++;
            } else {
                int t = passengers[j - 1];
                if (t == v) {
                    for (int k = j - 2; k >= 0; k--) {
                        if (passengers[k] != passengers[k + 1] - 1) {
                            return passengers[k + 1] - 1;
                        }
                    }

                    return passengers[0] - 1;
                } else {
                    return v;
                }

            }
            if (j == n) {
                if (capacity == 0 || passengers[j - 1] == v) {
                    for (int k = j - 2; k >= 0; k--) {
                        if (passengers[k] != passengers[k + 1] - 1) {
                            return passengers[k + 1] - 1;
                        }
                    }

                    return passengers[0] - 1;
                } else {
                    return v;
                }
            }
        }
        for (int k = j - 2; k >= 0; k--) {
            if (passengers[k] != passengers[k + 1] - 1) {
                return passengers[k + 1] - 1;
            }
        }
        return passengers[0] - 1;
    }

}
